/*-------------------------------------------------------------------------
 *
 * prepqual.c
 *	  预处理资格表达式的例程
 *
 *
 * 虽然解析器会从简单的 AND 的或 OR 的子句序列生成扁平（N-参数）AND/OR 树，但如果输入的括号奇怪，
 * 可能会出现一个 AND 子句直接在另一个 AND 下，或者 OR 在 OR 下。此外，规则扩展和子查询扁平化可能会生成这样的解析树。
 * 规划者希望扁平化所有这些情况，以确保一致的优化行为。
 *
 * 以前，本模块负责进行初步扁平化，但现在我们将其留给 eval_const_expressions 来完成，因为它无论如何都必须对表达式树进行完整遍历。
 * 相反，我们只需确保我们的操作保持 AND/OR 的扁平化。
 * pull_ands() 和 pull_ors() 用于在可能引入嵌套 AND/OR 的局部变换后保持 AND/OR 树的扁平化。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/optimizer/prep/prepqual.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/optimizer.h"
#include "optimizer/prep.h"
#include "utils/lsyscache.h"


static List *fc_pull_ands(List *fc_andlist);
static List *fc_pull_ors(List *fc_orlist);
static Expr *fc_find_duplicate_ors(Expr *fc_qual, bool fc_is_check);
static Expr *fc_process_duplicate_ors(List *fc_orlist);


/*
 * negate_clause
 *	   negate 一个布尔表达式。
 *
 * 输入是要否定的子句（例如，NOT 子句的参数）。
 * 返回一个新的子句，相当于给定子句的否定。
 *
 * 尽管可以单独调用，但它主要作为 eval_const_expressions() 的辅助工具，
 * 而该上下文驱动了几个设计决策。特别是，如果输入已经是 AND/OR 扁平的，
 * 我们必须保持这种属性。我们也不会在一些情况下递归，在这些情况下可以假设
 * eval_const_expressions 的低级执行已经简化了输入的子子句。
 *
 * 这与简单的 make_notclause() 的区别在于，这个尝试通过逻辑简化来消除 NOT 节点。
 * 如果可以彻底消除 NOT 节点，这显然总是一种成功。然而，我们对德摩根定律的使用
 * 可能导致有更多的 NOT 节点而不是更少。我们无论如何都这样做，因为在 WHERE 子句中
 * 重要的是尽可能暴露更多的顶层 AND/OR 结构。同时，消除中间的 NOT 可能让我们能够
 * 合并两个级别的 AND 或 OR 在一起，否则我们无法做到。最后，做这件事的动机之一是
 * 确保逻辑上等价的表达式会被视为物理上相等，因此我们应该始终应用相同的变换。
 */
Node * negate_clause(Node *fc_node)
{
	if (fc_node == NULL)			/* 不应该发生 */
		elog(ERROR, "can't negate an empty subexpression");
	switch (nodeTag(fc_node))
	{
		case T_Const:
			{
				Const	   *fc_c = (Const *) fc_node;

				/* NOT NULL 仍然是 NULL */
				if (fc_c->constisnull)
					return makeBoolConst(false, true);
				/* 否则相当简单 */
				return makeBoolConst(!DatumGetBool(fc_c->constvalue), false);
			}
			break;
		case T_OpExpr:
			{
				/*
				 * 如果可能，否定操作符：(NOT (< A B)) => (>= A B)
				 */
				OpExpr	   *fc_opexpr = (OpExpr *) fc_node;
				Oid			fc_negator = get_negator(fc_opexpr->opno);

				if (fc_negator)
				{
					OpExpr	   *fc_newopexpr = makeNode(OpExpr);

					fc_newopexpr->opno = fc_negator;
					fc_newopexpr->opfuncid = InvalidOid;
					fc_newopexpr->opresulttype = fc_opexpr->opresulttype;
					fc_newopexpr->opretset = fc_opexpr->opretset;
					fc_newopexpr->opcollid = fc_opexpr->opcollid;
					fc_newopexpr->inputcollid = fc_opexpr->inputcollid;
					fc_newopexpr->args = fc_opexpr->args;
					fc_newopexpr->location = fc_opexpr->location;
					return (Node *) fc_newopexpr;
				}
			}
			break;
		case T_ScalarArrayOpExpr:
			{
				/*
				 * 如果其操作符有否定符号，则否定一个 ScalarArrayOpExpr；
				 * 例如 x = ANY (list) 变成 x <> ALL (list)
				 */
				ScalarArrayOpExpr *fc_saopexpr = (ScalarArrayOpExpr *) fc_node;
				Oid			fc_negator = get_negator(fc_saopexpr->opno);

				if (fc_negator)
				{
					ScalarArrayOpExpr *fc_newopexpr = makeNode(ScalarArrayOpExpr);

					fc_newopexpr->opno = fc_negator;
					fc_newopexpr->opfuncid = InvalidOid;
					fc_newopexpr->hashfuncid = InvalidOid;
					fc_newopexpr->negfuncid = InvalidOid;
					fc_newopexpr->useOr = !fc_saopexpr->useOr;
					fc_newopexpr->inputcollid = fc_saopexpr->inputcollid;
					fc_newopexpr->args = fc_saopexpr->args;
					fc_newopexpr->location = fc_saopexpr->location;
					return (Node *) fc_newopexpr;
				}
			}
			break;
		case T_BoolExpr:
			{
				BoolExpr   *fc_expr = (BoolExpr *) fc_node;

				switch (fc_expr->boolop)
				{
						/*--------------------
						 * 应用德摩根定律：
						 *		(NOT (AND A B)) => (OR (NOT A) (NOT B))
						 *		(NOT (OR A B))	=> (AND (NOT A) (NOT B))
						 * 即，用 OR 替换 AND 并否定每个子句。
						 *
						 * 如果输入已经是 AND/OR 扁平且没有 NOT
						 * 直接在 AND 或 OR 之上，这种变换会保持
						 * 这些属性。例如，如果给定 AND 子句的
						 * 直接子代没有 AND 或 NOT-在-OR 之上，则
						 * negate_clause() 的递归调用不会返回任何
						 * OR 子句。因此我们不需要在构建新的 OR
						 * 子句之前调用 pull_ors()。对于 OR 情况也是如此。
						 *--------------------
						 */
					case AND_EXPR:
						{
							List	   *fc_nargs = NIL;
							ListCell   *fc_lc;

							foreach(fc_lc, fc_expr->args)
							{
								fc_nargs = lappend(fc_nargs,
												negate_clause(lfirst(fc_lc)));
							}
							return (Node *) make_orclause(fc_nargs);
						}
						break;
					case OR_EXPR:
						{
							List	   *fc_nargs = NIL;
							ListCell   *fc_lc;

							foreach(fc_lc, fc_expr->args)
							{
								fc_nargs = lappend(fc_nargs,
												negate_clause(lfirst(fc_lc)));
							}
							return (Node *) make_andclause(fc_nargs);
						}
						break;
					case NOT_EXPR:

						/*
						 * NOT 在 NOT 之下：它们相互抵消。我们假设输入已经
						 * 进行了简化，因此无需递归。
						 */
						return (Node *) linitial(fc_expr->args);
					default:
						elog(ERROR, "unrecognized boolop: %d",
							 (int) fc_expr->boolop);
						break;
				}
			}
			break;
		case T_NullTest:
			{
				NullTest   *fc_expr = (NullTest *) fc_node;

				/*
				 * 在行类型情况下，这两种 NullTest 并不是
				 * 逻辑逆，因此我们无法简化。但它确实适用于
				 * 标量数据类型。
				 */
				if (!fc_expr->argisrow)
				{
					NullTest   *fc_newexpr = makeNode(NullTest);

					fc_newexpr->arg = fc_expr->arg;
					fc_newexpr->nulltesttype = (fc_expr->nulltesttype == IS_NULL ?
											 IS_NOT_NULL : IS_NULL);
					fc_newexpr->argisrow = fc_expr->argisrow;
					fc_newexpr->location = fc_expr->location;
					return (Node *) fc_newexpr;
				}
			}
			break;
		case T_BooleanTest:
			{
				BooleanTest *fc_expr = (BooleanTest *) fc_node;
				BooleanTest *fc_newexpr = makeNode(BooleanTest);

				fc_newexpr->arg = fc_expr->arg;
				switch (fc_expr->booltesttype)
				{
					case IS_TRUE:
						fc_newexpr->booltesttype = IS_NOT_TRUE;
						break;
					case IS_NOT_TRUE:
						fc_newexpr->booltesttype = IS_TRUE;
						break;
					case IS_FALSE:
						fc_newexpr->booltesttype = IS_NOT_FALSE;
						break;
					case IS_NOT_FALSE:
						fc_newexpr->booltesttype = IS_FALSE;
						break;
					case IS_UNKNOWN:
						fc_newexpr->booltesttype = IS_NOT_UNKNOWN;
						break;
					case IS_NOT_UNKNOWN:
						fc_newexpr->booltesttype = IS_UNKNOWN;
						break;
					default:
						elog(ERROR, "unrecognized booltesttype: %d",
							 (int) fc_expr->booltesttype);
						break;
				}
				fc_newexpr->location = fc_expr->location;
				return (Node *) fc_newexpr;
			}
			break;
		default:
			/* 否则继续 */
			break;
	}

	/*
	 * 否则我们不知道如何简化此内容，因此只需附加一个
	 * 显式的 NOT 节点。
	 */
	return (Node *) make_notclause((Expr *) fc_node);
}


/*
 * canonicalize_qual
 *	  将资格表达式转换为最有用的形式。
 *
 * 这主要用于顶层 WHERE（或 JOIN/ON）
 * 子句。它也可以在顶层 CHECK 约束上使用，
 * 这时将 pass 的 is_check = true。不得在
 * 任何未知是否是其中之一的表达式上调用它，
 * 因为这可能会应用不当的简化。
 *
 * 这个例程的名称是一个遗留，来自于它试图
 * 强制表达式成规范的 AND-OR 或 OR-AND 形式的时代。
 * 最终，我们意识到这一点在理论上更纯洁，
 * 而不是实际有用，所以现在变换不涉及到达
 * 规范形式的任何概念。
 *
 * 注意：我们假设输入已经通过 eval_const_expressions
 * 处理，因此具有 AND/OR 扁平性。之前该函数
 * 包含自己的扁平逻辑，但那需要对树的
 * 不必要的额外遍历。
 *
 * 返回修改后的资格。
 */
Expr * canonicalize_qual(Expr *fc_qual, bool fc_is_check)
{
	Expr	   *fc_newqual;

	/* 空资格的快速退出 */
	if (fc_qual == NULL)
		return NULL;

	/* 不应在隐式 AND 格式的资格上调用此方法 */
	Assert(!IsA(fc_qual, List));

	/*
	 * 在 OR-AND 树中上移冗余子句。我们只在顶层 AND/OR
	 * 结构中执行此操作；没有必要深入查找。
	 * 同样，移除顶层结构中的任何 NULL 常量。
	 */
	fc_newqual = fc_find_duplicate_ors(fc_qual, fc_is_check);

	return fc_newqual;
}



/*
 * pull_ands
 *	  递归地将嵌套的 AND 子句扁平化为单个 and-clause 列表。
 *
 * 输入是 AND 子句的参数列表。
 * 返回重组后的参数列表（注意原始列表结构未被触及）。
 */
static List * fc_pull_ands(List *fc_andlist)
{
	List	   *fc_out_list = NIL;
	ListCell   *fc_arg;

	foreach(fc_arg, fc_andlist)
	{
		Node	   *fc_subexpr = (Node *) lfirst(fc_arg);

		if (is_andclause(fc_subexpr))
			fc_out_list = list_concat(fc_out_list,
								   fc_pull_ands(((BoolExpr *) fc_subexpr)->args));
		else
			fc_out_list = lappend(fc_out_list, fc_subexpr);
	}
	return fc_out_list;
}

/*
 * pull_ors
 *	  递归地将嵌套的 OR 子句扁平化为单个 or-clause 列表。
 *
 * 输入是 OR 子句的参数列表。
 * 返回重组后的参数列表（注意原始列表结构未被触及）。
 */
static List * fc_pull_ors(List *fc_orlist)
{
	List	   *fc_out_list = NIL;
	ListCell   *fc_arg;

	foreach(fc_arg, fc_orlist)
	{
		Node	   *fc_subexpr = (Node *) lfirst(fc_arg);

		if (is_orclause(fc_subexpr))
			fc_out_list = list_concat(fc_out_list,
								   fc_pull_ors(((BoolExpr *) fc_subexpr)->args));
		else
			fc_out_list = lappend(fc_out_list, fc_subexpr);
	}
	return fc_out_list;
}


/*--------------------
 * 以下代码试图应用逆 OR 分配律：
 *		((A AND B) OR (A AND C))  =>  (A AND (B OR C))
 * 也就是说，定位所有子子句包含相同术语的 OR 子句，并提取出重复的术语。
 *
 * 这似乎是一项相当无用的活动，但它实际上适用于许多机器生成的查询，以及一些 TPC 基准中的查询也需要这种处理。 事实上，这是旧的 prepqual 代码试图将查询强制转换为典型 AND-ORs 形式的几乎唯一有用的副作用： 
 * 		((A AND B) OR (A AND C))
 * 的典型等价形式是
 *		((A OR A) AND (A OR C) AND (B OR A) AND (B OR C))
 * 代码能够将其简化为
 *		(A AND (A OR C) AND (B OR A) AND (B OR C))
 * 从而成功提取出共同条件 A —— 但代价是使资格中充满了许多冗余的子句。
 *--------------------
 */

/*
 * find_duplicate_ors
 *	  给定一个将 NOT 推到底部的资格树，搜索可能应用逆 OR 分配律的 OR 子句。
 *	  仅搜索顶层的 AND/OR 结构。
 *
 * 在此过程中，我们删除顶层 AND/OR 结构中的任何 NULL 常量，例如在 WHERE 子句中，“x OR NULL::boolean”被简化为“x”。
 * 通常这会改变结果，因此 eval_const_expressions 无法做到这一点；但在 WHERE 的顶层，我们不需要区分 FALSE 和 NULL 结果，因此将 NULL::boolean 视为 FALSE 并然后相应地简化 AND/OR 是有效的。 反之，在顶层 CHECK 约束中，我们可以将 NULL 视为 TRUE。
 *
 * 返回修改后的资格。AND/OR 的扁平性得以保留。
 */
static Expr * fc_find_duplicate_ors(Expr *fc_qual, bool fc_is_check)
{
	if (is_orclause(fc_qual))
	{
		List	   *fc_orlist = NIL;
		ListCell   *fc_temp;

		/* Recurse */
		foreach(fc_temp, ((BoolExpr *) fc_qual)->args)
		{
			Expr	   *fc_arg = (Expr *) lfirst(fc_temp);

			fc_arg = fc_find_duplicate_ors(fc_arg, fc_is_check);

			/* 去除任何常量输入 */
			if (fc_arg && IsA(fc_arg, Const))
			{
				Const	   *fc_carg = (Const *) fc_arg;

				if (fc_is_check)
				{
					/* 在 CHECK 的 OR 中，去掉常量 FALSE */
					if (!fc_carg->constisnull && !DatumGetBool(fc_carg->constvalue))
						continue;
					/* 常量 TRUE 或 NULL，OR 简化为 TRUE */
					return (Expr *) makeBoolConst(true, false);
				}
				else
				{
					/* 在 WHERE 的 OR 中，去掉常量 FALSE 或 NULL */
					if (fc_carg->constisnull || !DatumGetBool(fc_carg->constvalue))
						continue;
					/* 常量 TRUE，OR 简化为 TRUE */
					return fc_arg;
				}
			}

			fc_orlist = lappend(fc_orlist, fc_arg);
		}

		/* 将拉到这里下面的任何 OR 扁平化 */
		fc_orlist = fc_pull_ors(fc_orlist);

		/* 现在我们可以寻找重复的 OR */
		return fc_process_duplicate_ors(fc_orlist);
	}
	else if (is_andclause(fc_qual))
	{
		List	   *fc_andlist = NIL;
		ListCell   *fc_temp;

		/* Recurse */
		foreach(fc_temp, ((BoolExpr *) fc_qual)->args)
		{
			Expr	   *fc_arg = (Expr *) lfirst(fc_temp);

			fc_arg = fc_find_duplicate_ors(fc_arg, fc_is_check);

			/* 去除任何常量输入 */
			if (fc_arg && IsA(fc_arg, Const))
			{
				Const	   *fc_carg = (Const *) fc_arg;

				if (fc_is_check)
				{
					/* 在 CHECK 中的 AND，丢弃常量 TRUE 或 NULL */
					if (fc_carg->constisnull || DatumGetBool(fc_carg->constvalue))
						continue;
					/* 常量 FALSE，因此 AND 降低为 FALSE */
					return fc_arg;
				}
				else
				{
					/* 在 WHERE 中的 AND，丢弃常量 TRUE */
					if (!fc_carg->constisnull && DatumGetBool(fc_carg->constvalue))
						continue;
					/* 常量 FALSE 或 NULL，因此 AND 降低为 FALSE */
					return (Expr *) makeBoolConst(false, false);
				}
			}

			fc_andlist = lappend(fc_andlist, fc_arg);
		}

		/* 展平这里刚引入的任何 AND */
		fc_andlist = fc_pull_ands(fc_andlist);

		/* 没有输入的 AND 降低为 TRUE */
		if (fc_andlist == NIL)
			return (Expr *) makeBoolConst(true, false);

		/* 单表达式 AND 降低为该表达式 */
		if (list_length(fc_andlist) == 1)
			return (Expr *) linitial(fc_andlist);

		/* 否则我们仍然需要一个 AND 节点 */
		return make_andclause(fc_andlist);
	}
	else
		return fc_qual;
}

/*
 * process_duplicate_ors
 *	  给定一组被 OR 连接的表达式，尝试应用
 *	  反向 OR 分配法则。
 *
 * 返回结果表达式（可能是 AND 子句、OR 子句，或甚至是单个子表达式）。
 */
static Expr * fc_process_duplicate_ors(List *fc_orlist)
{
	List	   *fc_reference = NIL;
	int			fc_num_subclauses = 0;
	List	   *fc_winners;
	List	   *fc_neworlist;
	ListCell   *fc_temp;

	/* 没有输入的 OR 降低为 FALSE */
	if (fc_orlist == NIL)
		return (Expr *) makeBoolConst(false, false);

	/* 单表达式 OR 降低为该表达式 */
	if (list_length(fc_orlist) == 1)
		return (Expr *) linitial(fc_orlist);

	/*
	 * 选择最短的 AND 子句作为参考列表——显然，任何
	 * 不在该子句中的子子句并不在所有子句中。如果我们找到一个
	 * 不是 AND 的子句，我们可以将其视为一个元素的 AND 子句，
	 * 这必然是最短的。
	 */
	foreach(fc_temp, fc_orlist)
	{
		Expr	   *fc_clause = (Expr *) lfirst(fc_temp);

		if (is_andclause(fc_clause))
		{
			List	   *fc_subclauses = ((BoolExpr *) fc_clause)->args;
			int			fc_nclauses = list_length(fc_subclauses);

			if (fc_reference == NIL || fc_nclauses < fc_num_subclauses)
			{
				fc_reference = fc_subclauses;
				fc_num_subclauses = fc_nclauses;
			}
		}
		else
		{
			fc_reference = list_make1(fc_clause);
			break;
		}
	}

	/*
	 * 以防万一，消除参考列表中的任何重复项。
	 */
	fc_reference = list_union(NIL, fc_reference);

	/*
	 * 检查参考列表的每个元素，看它是否在所有 OR
	 * 子句中。构建一个新的赢家子句列表。
	 */
	fc_winners = NIL;
	foreach(fc_temp, fc_reference)
	{
		Expr	   *fc_refclause = (Expr *) lfirst(fc_temp);
		bool		fc_win = true;
		ListCell   *fc_temp2;

		foreach(fc_temp2, fc_orlist)
		{
			Expr	   *fc_clause = (Expr *) lfirst(fc_temp2);

			if (is_andclause(fc_clause))
			{
				if (!list_member(((BoolExpr *) fc_clause)->args, fc_refclause))
				{
					fc_win = false;
					break;
				}
			}
			else
			{
				if (!equal(fc_refclause, fc_clause))
				{
					fc_win = false;
					break;
				}
			}
		}

		if (fc_win)
			fc_winners = lappend(fc_winners, fc_refclause);
	}

	/*
	 * 如果没有赢家，我们无法转换 OR
	 */
	if (fc_winners == NIL)
		return make_orclause(fc_orlist);

	/*
	 * 生成新的 OR 列表，由剩余的子子句组成。
	 *
	 * 如果任何子句退化为空，那么我们就有像（A
	 * AND B）OR（A）这样的情况，这可以简化为仅 A——也就是说
	 * OR 的其他分支中的附加条件是无关紧要的。
	 *
	 * 请注意，由于我们使用 list_difference，AND 子句中
	 * 赢家子句的任何多次出现将被自动删除。
	 */
	fc_neworlist = NIL;
	foreach(fc_temp, fc_orlist)
	{
		Expr	   *fc_clause = (Expr *) lfirst(fc_temp);

		if (is_andclause(fc_clause))
		{
			List	   *fc_subclauses = ((BoolExpr *) fc_clause)->args;

			fc_subclauses = list_difference(fc_subclauses, fc_winners);
			if (fc_subclauses != NIL)
			{
				if (list_length(fc_subclauses) == 1)
					fc_neworlist = lappend(fc_neworlist, linitial(fc_subclauses));
				else
					fc_neworlist = lappend(fc_neworlist, make_andclause(fc_subclauses));
			}
			else
			{
				fc_neworlist = NIL;	/* 退化情况，见上文 */
				break;
			}
		}
		else
		{
			if (!list_member(fc_winners, fc_clause))
				fc_neworlist = lappend(fc_neworlist, fc_clause);
			else
			{
				fc_neworlist = NIL;	/* 退化情况，见上文 */
				break;
			}
		}
	}

	/*
	 * 如果还不退化，则将简化的 OR 附加到赢家列表，
	 * 正确处理单个元素的特殊情况（这真的会发生吗？）。
	 * 还要小心保持 AND/OR 的平整，以防我们提取了一个
	 * 子子 OR 子句。
	 */
	if (fc_neworlist != NIL)
	{
		if (list_length(fc_neworlist) == 1)
			fc_winners = lappend(fc_winners, linitial(fc_neworlist));
		else
			fc_winners = lappend(fc_winners, make_orclause(fc_pull_ors(fc_neworlist)));
	}

	/*
	 * 并返回构建好的 AND 子句，再次对单个元素和 AND/OR
	 * 的平整保持警惕。
	 */
	if (list_length(fc_winners) == 1)
		return (Expr *) linitial(fc_winners);
	else
		return make_andclause(fc_pull_ands(fc_winners));
}
